package chml;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;


public class AssitClass {

	/*
	 * 获取window的前缀长度 
	 */
	public static int PrefixLength(String[] window, int t, int w) {
		
		int coverage = 0;
		int ni = 0;
		int l;
		
		for(l = 0; l < w; l++){
			int i = GetTokenClass(window[l]);//获取token所属分区
			ni = ni + 1;
			if(ni >= i){
				coverage = coverage + 1;
				if(coverage == (t + 1)){
					break;
				}
			}
		}
		
		return l;
	}
	
	/*
	 * 产生window的所有signatures
	 */
	public static Set<String> GenSignature(String[] window, int t, int kmax, int w){
		Set<String> set = new HashSet<String>();
		int l = PrefixLength(window, t, w);//获取window的前缀长度
		ArrayList<String> piList = new ArrayList<String>();//存储属于第i类的tokens
		for(int i = 1; i <= kmax; i++){
			//获取属于第i类的tokens
			for(int k = 0; k < l; k++){
				if(GetTokenClass(window[k]) == i){
					piList.add(window[k]);
				}
			}
			if(piList.size() != 0){
				Set<String> iWiseSet = getIWiseSignatures(piList, i);
				set.addAll(iWiseSet);
			}
			piList.clear();
		}
		return set;
	}
	
	/*
	 * KWise分区算法
	 */
	public static Set<WindowPair> PartitionedKWise(String[] document, String[] query, int w, int t, int kmax){
		Set<WindowPair> ret = new HashSet<WindowPair>();
		
		if(document.length < w){
			System.out.println("document is too short");
			return null;
		}
		if(query.length < w){
			System.out.println("query is too short");
			return null;
		}
		
		HashMap<String, ArrayList<String[]>> docMap = new HashMap<String, ArrayList<String[]>>();
		//获取document的signature-windows映射列表
		for(int i = 0; i <= (document.length - w); i++){
			//获取第i个window
			String[] window = getWindow(document, i, w);
			
			//获取该window的signatures
			Set<String> sigSet = GenSignature(window, t, kmax, w);
			
			//构建signature-window的映射列表
			for (String sig : sigSet) {
				if(docMap.containsKey(sig)){
					docMap.get(sig).add(window);
				}else{
					ArrayList<String[]> tempList = new ArrayList<String[]>();
					tempList.add(window);
					docMap.put(sig, tempList);
				}
			}
		}
		
		//对每个query的window进行匹配检验
		for(int i = 0; i <= (query.length - w); i++){
			//获取第i个window
			String[] window = getWindow(query, i, w);
			
			//初始化一个ArrayList用于存储candidate
			Set<String[]> candidates = new HashSet<String[]>();
			
			//获取该window的signatures
			Set<String> sigSet = GenSignature(window, t, kmax, w);
			
			//从docMap寻找每个signature对应的candidates
			for (String sig : sigSet) {
				if(docMap.containsKey(sig)){
					for(String[] xStrings: docMap.get(sig)){
						candidates.add(xStrings);
					}
				}
			}
			
			//检验每个candidates是否合格
			for(String[] candidate: candidates){
				if(getWindowCommon(candidate, window) >= (w - t)){
					WindowPair pair = new WindowPair(candidate, window);
					ret.add(pair);
				}
			}
		}
		
		return ret;
	}
	
	//获取某个token所属的class
	public static int GetTokenClass(String str) {
		return DataProcess.getTokenClass(str);
	}
	
	//获取某个集合的i-wise所有signatures组合
	public static Set<String> getIWiseSignatures(ArrayList<String> pi, int i){
		Set<String> ret = new HashSet<String>();
		
		if(pi.size() < i){//若token的数量小于类号i，则直接返回
			
			for(int k = 0; k < pi.size(); k++){
				ret.addAll(pi);
			}
			return ret;
		}
		
		//获取数组pi的所有i项组合
		/*for(int k = 0; k <= (pi.size() - i); k++){
			ArrayList<String> temp = new ArrayList<String>();
			combine(temp, pi, i, k);
			ret.addAll(temp);
			temp.clear();
		}*/
		ArrayList<String> temp = new ArrayList<String>();
		combine(ret, temp, pi, i, 0);
		
		return ret;
	}
	
	//获取数组的所有i项组合
	public static void combine(Set<String> ret, ArrayList<String> result, ArrayList<String> data, int number, int start){
		if(number == 0){
			String tempString = "";
			for(String s: result){
				tempString += s + " ";
			}
			ret.add(tempString.substring(0, tempString.length() - 1));
			//System.out.println(tempString.substring(0, tempString.length() - 1));
			return;
		}
		if(start == (data.size() - number)){
			//System.out.println("start == data.size()");
			return;
		}
		
		result.add(data.get(start));
		combine(ret, result, data, number - 1, start + 1);
		result.remove((String)data.get(start));
		combine(ret, result, data, number, start + 1);
	}
	
	//根据文档和偏移量获取window
	public static String[] getWindow(String[] document, int i, int w) {
		String[] ret = new String[w];
		for(int k = 0; k < w; k++){
			ret[k] = document[k + i];
		}
		return ret;
	}
	
	//获取两个window的差异量
	public static int getWindowCommon(String[] docWindow, String[] queryWindow){
		int common = 0;
		
		String[] docCopy = Arrays.copyOf(docWindow, docWindow.length);
		String[] queryCopy = Arrays.copyOf(queryWindow, queryWindow.length);
		
		for(String query: queryCopy){
			for(int i = 0; i < docCopy.length; i++){
				String doc = docCopy[i];
				if(query.equals(doc)){
					docCopy[i] = null;
					common++;
					break;
				}
			}
		}
		
		return common;
	}
}
